/*  slffctpf.cpp  by K.Tsuru  */
// function ID 2009   DRADIX    since ver 2.181
/***********************************************************
 N!(N >= 5)
 factorial by prime factorization method and tournament product
 refer to GMP's factorial algorithm using prime factorization

But the recursive call is not used such as the typical example
of binary splitting method.

Nov 26 2016
         timing(sec)
   N   |   FactPF  figures
  10^5 |   0.12      456,574
2*10^6 |   3.40   11,733,475 ... exclude fftMaxArraySize = 2^20 =1,048,576
2*10^7 |  76.84  137,334,715 FFTUsedTimes() = 160650
1000003(a prime number) 1.51
***********************************************************/
#ifndef SN_H
#include "sn.h"
#endif

/*********************************************
For pull out the power of 10
2^p * 5^q ==> 2^(p-q) * 10^q (of course p > q)
**********************************************/
const int POS2 = 0; // position of "2" in {2,3,5,7,....}
const int POS5 = 2; // position of "5" in {2,3,5,7,....}

SLong FactPF(ulong N) {
    if(N <= 20) return factD(N); // since version 2.30
    SNBlock<primeFactor> pf;
    int npf = FactorialIntoPrimeFactor(N, pf);// 'npf' is the number of prime factor
    int pow10 = pf[POS5].power; // the power of 10
    pf[POS2].power -= pow10;    // reduce the power of 2

    // exclude "5"
    npf--;
    int i;
    for(i = POS5; i < npf; i++) pf[i] = pf[i+1]; // Default assignment operator is used for the structure "primeFactor".
    pf[i].power = pf[i].prime = 0;

    SLong Q = PrimeFactorProduct(pf, npf);
    Q.MultPow10(pow10); // Q*10^pow10 in which shifting array elements is used.
    return Q;
}